<!DOCTYPE html>
<html>

  <head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1">

  <title>
    编译器开发从零单排(1)
    </title>
  <link type="application/atom+xml" rel="alternate" href="/feed.xml" title="虚实" />
  
  <style>
  table{
    border-left:1px solid #000000;border-top:1px solid #000000;
    width: 100%;
    word-wrap:break-word; word-break:break-all;
  }
  table th{
  text-align:center;
  }
  table th,td{
    border-right:1px solid #000000;border-bottom:1px solid #000000;
  }
  </style>

  <meta name="description" content="前言">
  <link rel="stylesheet" href="/css/main.css">
  <link rel="stylesheet" href="/css/toc.css">
  <link rel="canonical" href="/2019/02/16/%E7%BC%96%E8%AF%91%E5%99%A8%E5%BC%80%E5%8F%91%E4%BB%8E%E9%9B%B6%E5%8D%95%E6%8E%92%281%29/">
  <link rel="alternate" type="application/rss+xml" title="虚实" href="/feed.xml" />
  <link rel="stylesheet" href="/css/highlight.min.css">
  <link href="//cdn.staticfile.org/font-awesome/3.2.1/css/font-awesome.min.css" rel="stylesheet"media="all">
</head>


  <body>

    <header class="site-header">

  <div class="wrapper">
    <div>
      <a class="site-title" href="/">虚实</a>
      <div class="site-pages">
		<a class="site-page" href="/archive/">归档</a>
		<a class="site-page" href="/categories/">分类</a>
		<a class="site-page" href="/about/">关于</a>
		<a class="site-page" href="/friend-links/">友情链接</a>
        <a class="site-page" href="/recommends/">推荐</a>
      </div>
      <p class="site-sub-title">记录下折腾和学习的过程</p>
    </div>

  </div>

</header>


    <div class="page-content">
      <div class="wrapper">
        <div class="post">

  <header class="post-header">
    <h1 class="post-title">编译器开发从零单排(1)</h1>
    <p class="post-meta">Feb 16, 2019 • admin</p>

	<p class="post-meta"> categories :   <a href="/categories/#compiler"> compiler </a>  </p>
    <div id="show_qrcode">
        <a>扫描二维码</a>
        <div id="qrcode" style="display:none;position:absolute;z-index:1"></div>
    </div>
  </header>
  <div class="nav">
      <div id="toc" class="toc"></div>
  </div>
  <article class="post-content">
    <h2 id="前言">前言</h2>

<p>几年之前就想写一个系列的博客，记录一下从大学上完编译原理课后，不断尝试自己编写一个 C 语音编译器的过程。</p>

<p>在不断尝试的过程中，最大的感触有两个。</p>

<ul>
  <li>
    <p>不要太高估自己的时间和精力，不要把目标定的太高。</p>

    <p>做为互联网公司中的一线开发人员，在KPI的压力下，能够完成工作内容并学习一些工作相关的知识，已经很不容易了。只有在偶尔不加班的周末，或者下班以后十一二点到凌晨两点的安静的夜晚，才有时间分给写业余的出于爱好的代码，这也是工作之后写代码写的最开心的时间了。</p>
  </li>
  <li>
    <p>参考成熟的大型的有广泛应用的项目代码(Clang, LLVM)，先模仿学习。</p>

    <p>结合理论阅读、调试代码，尝试把其每一步生成中间结果的步骤和逻辑分清楚。在此基础上选择自己熟悉的工具，设计好整个项目再分步实现。</p>
  </li>
</ul>

<p>这些尝试产生的结果即为 <a href="https://github.com/Mithrilwoodrat/naivecompiler">naivecompiler</a>，一个由 Python、C++ 混合编写，基于 PLY 和 LLVM 的 C 语言子集编译器。</p>

<p>本来是打算先实现了计划中要支持的所有特性再开始写博客的，可是随着一年年的工作，发现要像国外的程序员抽出完整的时间做自己的 Side Project 是件过于奢侈的事，完成所有的特性遥遥无期。只能从长计议，边写代码边写博客，记录下学习过的理论知识、读源码的感悟、调试的心得，免得还没等到写完那一天就把这些都忘光了。</p>

<p>该项目主要参考 《编译原理》（龙书）， <a href="https://github.com/eliben/pycparser">pycparser</a>， <a href="https://github.com/dabeaz/ply">PLY</a> 以及部分 GCC 和 <a href="https://github.com/llvm-mirror/clang">Clang</a> 的代码。</p>

<p>以及使用 Clang 的命令行参数，dump 出每一步的中间结果，用于参考。</p>

<h2 id="典型编译器的结构">典型编译器的结构</h2>
<p>一个典型的静态语言编译器一般分为以下几个部分</p>

<ul>
  <li>词法分析 (Lexical analysis)</li>
  <li>语法分析 (Syntax analysis)</li>
  <li>语义分析 (Semantic analysis)</li>
  <li>中间代码生成 (Intermediate representation code generation)</li>
  <li>平台无关的代码优化 (Machine independent optimizations)</li>
  <li>代码生成 (Code generation)</li>
  <li>平台相关的代码优化 (Machine dependent optimizations)</li>
  <li>目标文件的生成 (Object File generation)</li>
</ul>

<p align="center">
  <img src="/imgs/compiler_construction.png" />
</p>

<p>在此之外，将目标文件链接为可执行文件或者动态、静态链接库虽然是属于链接器的工作，但日常使用中我们一般也是通过编译器命令完成链接的过程，如 <code class="language-plaintext highlighter-rouge">gcc hello.c -o hello</code> ，该命令最终会生成一个名为 hello 的 ELF 可执行文件。</p>

<p>根据维基百科上 <a href="https://en.wikipedia.org/wiki/Compiler">Compiler</a> 的定义，
一个 Compiler 可以分为 3 部分，即 Front end、Middle end、Back end。</p>

<p>上面提到的 8 个步骤中，词法分析、语法分析、语义分析、中间代码生成属于 Front end，平台无关的代码优化属于 Middle end，代码生成、平台相关的代码优化、目标文件的生成则属于 Back end。</p>

<p>在 Clang 中，大致的编译流程为经过词法、语法分析后生成 AST。然后基于 AST 生成 CFG 进行各类 Analysis，然后也基于 AST 划分 BasicBlock ，调用 LLVM 进行代码生成。上述的流程是基于之前阅读 Clang 源码后凭记忆得出，同时也参考了 Github 上有人写过的 <a href="https://github.com/yejinlei/about-compiler/blob/master/%E6%9C%89%E5%85%B3LLVM.md#clang%E6%B5%81%E7%A8%8B%E5%88%86%E6%9E%90">clang 流程分析</a>，如有错误请不吝赐教。</p>

<h2 id="naivecompiler-的框架设计">naivecompiler 的框架设计</h2>

<p><a href="https://github.com/Mithrilwoodrat/naivecompiler">naivecompiler</a> 中，前端的词法、语法、语义分析是用 Python 基于 PLY 框架实现的，后续的中间代码生成、和基于中间代码的分析也是基于 Python 实现。生成好中间代码后以序列化的方式生成中间文件，然后在 C++ 后读取序列化文件。代码生成以及后端的优化、目标文件生成都是在 C++ 中封装 llvm api 实现。</p>

<h3 id="目录结构">目录结构</h3>

<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>naivecompiler git:(llvm-6.0) tree -C -L 1
.
├── Docker
├── README.md
├── Structure.py
├── analysis_handler.py
├── ast_rewrite.py
├── backend
├── build.sh
├── c_ast.py
├── c_parser.py
├── cfgbuilder.py
├── clean.sh
├── codegen.py
├── compiler.py
├── demo
├── interface.py
├── libNaiveScript.so
├── link.sh
├── llvm.py
├── ns.data
├── parser.out
├── parsetab.py
├── requirements.txt
├── serialize_handler.py
├── serialize_structure.py
├── symbol_table.py
├── test.sh
├── tests
└── visitor.py
</code></pre></div></div>

<p>其中，<code class="language-plaintext highlighter-rouge">compiler.py</code> 为整个项目的入口。编译的过程为:</p>
<ul>
  <li>调用 <code class="language-plaintext highlighter-rouge">c_parser.py</code> 中的词法、语法分析模块，按 <code class="language-plaintext highlighter-rouge">c_ast.py</code> 生成 AST。</li>
  <li>然后调用 <code class="language-plaintext highlighter-rouge">codegen.py</code> 中的<code class="language-plaintext highlighter-rouge">build_basic_blocks</code> 将 AST 按 basic block 划分，生成中间代码。</li>
  <li><code class="language-plaintext highlighter-rouge">compile</code> 函数中调用 <code class="language-plaintext highlighter-rouge">SerializeHandler</code> 将 AST 序列化，并调用 <code class="language-plaintext highlighter-rouge">dump_stringtable</code> 将环境变量中的字符串表一同序列化生成最后的序列化文件。</li>
  <li>加载后端 c++ 链接库，读取序列化文件。</li>
  <li>后端解析序列化文件，调用 LLVM API 生成 LLVM IR。</li>
  <li>根据 IR 调用 LLVM API 生成对应的目标文件。</li>
</ul>

<h2 id="总结">总结</h2>

<p>在后续的几篇文章中，我们将陆续分前后端以 NaiveCompiler 和 Clang 为例介绍一个C语言子集的典型的静态编译器的各个部分，以及 PLY 和 LLVM 的使用和编译器编写中常用的模式和数据结构。</p>

<ul>
  <li><a href="/2019/02/16/编译器开发从零单排%282%29/">编译器开发从零单排(2)</a> 中将介绍如何使用 PLY 进行词法、语法分析，生成 AST。</li>
</ul>

<h2 id="refs">Refs</h2>
<ul>
  <li>https://norasandler.com/2017/11/29/Write-a-Compiler.html</li>
  <li>https://dsprenkels.com/compiler-construction.html</li>
</ul>

  </article>

</div>
<div id="disqus_thread"></div>
<script type="text/javascript">
    /* * * CONFIGURATION VARIABLES * * */
    var disqus_shortname = 'yoursoulismine';
    
    /* * * DON'T EDIT BELOW THIS LINE * * */
    (function() {
        var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
        dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
        (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
    })();
</script>
<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript" rel="nofollow">comments powered by Disqus.</a></noscript>
<script type="text/javascript">
    /* * * CONFIGURATION VARIABLES * * */
    var disqus_shortname = 'yoursoulismine';
    
    /* * * DON'T EDIT BELOW THIS LINE * * */
    (function () {
        var s = document.createElement('script'); s.async = true;
        s.type = 'text/javascript';
        s.src = '//' + disqus_shortname + '.disqus.com/count.js';
        (document.getElementsByTagName('HEAD')[0] || document.getElementsByTagName('BODY')[0]).appendChild(s);
    }());
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/raphael/2.1.0/raphael-min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.11.0/jquery.min.js"></script>
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/js/bootstrap.min.js"></script>
<script src="https://flowchart.js.org/flowchart-latest.js"></script>
<script src="/js/highlight.min.js"></script>
<script src="/js/toc.js"></script>
<script src="/js/qrcode.min.js"></script>
<script>
if (!String.prototype.format) {
    String.prototype.format = function() {
        var args = arguments;
        return this.replace(/{(\d+)}/g, function(match, number) { 
            return typeof args[number] != 'undefined'
                ? args[number]
                : match
            ;
        });
    };
}

$('pre code').each(function(i, block) {
    hljs.highlightBlock(block);
});

$('.language-flow').each(function(i, block) {
    console.log(block);
    code = $(this).text();
    diagram = flowchart.parse(code);
    canvas_id = 'flow'+ i;
    console.log(canvas_id);
    temp = "<div id='{0}'> </div>".format(canvas_id);
    console.log(temp);
    $(this).html(temp);
    diagram.drawSVG(canvas_id, {
        'x': 0,
        'y': 0,
        'line-width': 3,
        'line-length': 50,
        'text-margin': 10,
        'font-size': 14,
    });	
});

$('#toc').toc({
    noBackToTopLinks: true,
    listType: 'ul',
    title: 'TOC',
});

var url = location.href;
console.log(url);
var qrcode = new QRCode("qrcode", {
    text: url,
    width: 128,
    height: 128,
    colorDark : "#000000",
    colorLight : "#ffffff",
    correctLevel : QRCode.CorrectLevel.H
});

$(document).ready(function () {
    $('#show_qrcode').on('mouseenter', function () {
        $('#qrcode').show();
        $(this).css({
            "text-decoration": "underline"
        });
    }).on('mouseleave', function () {
        $('#qrcode').hide();
        $(this).css({
            "text-decoration": ''
        });
    });;
});
</script>

      </div>
    </div>

    <footer class="site-footer">

  <div class="wrapper">


    <div class="footer-col-wrapper">
      <div class="footer-col  footer-col-1">
        <ul class="contact-list">
	  <li>
          <li><a href="mailto:mithrilwoodrat@gmail.com">mithrilwoodrat@gmail.com</a></li>
        </ul>
      </div>

      <div class="footer-col  footer-col-2">
        <ul class="social-media-list">
          
          <li>
            <a href="https://github.com/Mithrilwoodrat">
              <span class="icon  icon--github">
                <svg viewBox="0 0 16 16">
                  <path fill="#828282" d="M7.999,0.431c-4.285,0-7.76,3.474-7.76,7.761 c0,3.428,2.223,6.337,5.307,7.363c0.388,0.071,0.53-0.168,0.53-0.374c0-0.184-0.007-0.672-0.01-1.32 c-2.159,0.469-2.614-1.04-2.614-1.04c-0.353-0.896-0.862-1.135-0.862-1.135c-0.705-0.481,0.053-0.472,0.053-0.472 c0.779,0.055,1.189,0.8,1.189,0.8c0.692,1.186,1.816,0.843,2.258,0.645c0.071-0.502,0.271-0.843,0.493-1.037 C4.86,11.425,3.049,10.76,3.049,7.786c0-0.847,0.302-1.54,0.799-2.082C3.768,5.507,3.501,4.718,3.924,3.65 c0,0,0.652-0.209,2.134,0.796C6.677,4.273,7.34,4.187,8,4.184c0.659,0.003,1.323,0.089,1.943,0.261 c1.482-1.004,2.132-0.796,2.132-0.796c0.423,1.068,0.157,1.857,0.077,2.054c0.497,0.542,0.798,1.235,0.798,2.082 c0,2.981-1.814,3.637-3.543,3.829c0.279,0.24,0.527,0.713,0.527,1.437c0,1.037-0.01,1.874-0.01,2.129 c0,0.208,0.14,0.449,0.534,0.373c3.081-1.028,5.302-3.935,5.302-7.362C15.76,3.906,12.285,0.431,7.999,0.431z"/>
                </svg>
              </span>
              <span class="username">Mithrilwoodrat</span> 
            </a>
          </li>
          
        </ul>
      </div>
  </div>
</footer>

<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

  ga('create', 'UA-66599686-1', 'auto');
  ga('send', 'pageview');

</script>
</body>
</html>
